# 给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链
# 表节点，返回 反转后的链表 。
# 
#  
# 
#  示例 1： 
#  
#  
# 输入：head = [1,2,3,4,5], left = 2, right = 4
# 输出：[1,4,3,2,5]
#  
# 
#  示例 2： 
# 
#  
# 输入：head = [5], left = 1, right = 1
# 输出：[5]
#  
# 
#  
# 
#  提示： 
# 
#  
#  链表中节点数目为 n 
#  1 <= n <= 500 
#  -500 <= Node.val <= 500 
#  1 <= left <= right <= n 
#  
# 
#  
# 
#  进阶： 你可以使用一趟扫描完成反转吗？ 
# 
#  Related Topics 链表 👍 1901 👎 0
from typing import Optional

from LeetCode.Test.LinkTool import ListNode, LinkedListTool, Link


# leetcode submit region begin(Prohibit modification and deletion)
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
        if head is None or head.next is None:
            return head
        # 虚构一个头节点
        newhead = ListNode()
        newhead.next = head

        cur = head
        if left - 2 >= 0:
            for i in range(left - 2):
                cur = cur.next
            leftPreNode = cur
        else:
            leftPreNode = newhead

        cur = head
        for i in range(right - 1):
            cur = cur.next
        rightNode = cur
        # 找好边界后，开始循环交换
        rightNexrNode = rightNode.next
        curr = leftPreNode.next
        pre = rightNode.next
        # 循环到右边界停止
        while curr != rightNexrNode:
            next_node = curr.next
            curr.next = pre
            pre = curr
            curr = next_node
        leftPreNode.next = rightNode
        return newhead.next


# leetcode submit region end(Prohibit modification and deletion)
Link.each(Solution().reverseBetween(LinkedListTool([1, 2, 3, 4, 5]), 2, 4))
